
#include "common.h"
#include "KBigNum.h"
#include "Sort.h"
using namespace std;

int getGreaterCount(int * array, int arrayLen,  int splitter) 
{
    int count = 0;
    for(int i = 0; i < arrayLen; i++)
        if( array[i] >= splitter)
            count ++;

    return count;
}

void getKBigNum_kthMax(int * array , int arrayLen, int k)
{
    int min = 1000;
    int max = 0;
    int mid = 500;
    for(int i = 0; i < arrayLen; i++)
    {
        if(array[i] < min)
            min = array[i];
        if(array[i] > max)
            max = array[i];
    }

    while ( max - min > 1)
    {
       mid = min + (max - min)* 0.5;
       if(getGreaterCount(array, arrayLen, mid) >= k)
           min = mid;
       else
           max = mid;
    }

    //min is the number we need.
	cout << "The kth Max number is " << min << endl;
    cout << "min = " << min << " max = " << max << " mid = " << mid << endl;

}

void getKBigNum_quicksort(int * array , int arrayLen, int k)
{
	quickSort(array, 0, arrayLen-1);

	for(int i = arrayLen - 1; i > arrayLen - k - 1; i--)
		std::cout << array[i] << "  ";
}

void getKBigNum_partsort(int * array , int arrayLen, int k)
{
	partSort(array, 0, arrayLen -1, k);
}

void partSort(int * array, int startIndex, int endIndex, int k)
{
	if (endIndex - startIndex < 0)
	{
		return;
	}

	if(k <= 0)
	{
		return;
	}

    int baseIndex = random()%(endIndex - startIndex + 1) + startIndex;

    int swapTmp = array[baseIndex];
    array[baseIndex] = array[startIndex];
    array[startIndex] = swapTmp;

    
	//这个base实际像是被挖空的位置, 在最后一步把合适的值填上去.
	int base = array[startIndex];
	int i = startIndex, j = endIndex;

	while(i < j)
	{
		while(i < j && array[j] >= base)
			j--;
		//j位置是第一个 < base的位置.

		//把j位置的数给当前空位i. j位置空下来. i已经是小于Base, 所以i主动+1
		if(i < j)
		    array[i++] = array[j];

		while(i < j && array[i] < base) // 从左向右找第一个大于等于x的数
		    i++;
		//i位置是第一个>=base的位置.

		//把i当前位置大的这个数给空下来的j位置. i被挖空.
		if(i < j)
			array[j--] = array[i];
	}

	array[i] = base;

    if(endIndex - i + 1 <= k)  // k == 1 && i == startIndex == endIndex, we will output the final one.
    {
        for(int res = i; res <= endIndex; res++)
            cout << array[res] << "  ";

        partSort(array, startIndex, i-1, k - endIndex + i - 1);
    }
    else
    {
    	partSort(array, i + 1, endIndex, k);
    }
}

/* 用最小堆来实现找到最大的K个数.
 * 构建一个K大小的最小堆,将剩下的元素一个一个加入堆中,把最小的替换掉,
 * 当把所有元素都加入后,此时堆中的就是最大的K个数.
 */
void KHeapMaxNum(int * allEle,  int size, int K)
{
    if( size <=0 || K <= 0 ||  K > size)
        return;

    if(K==size)
    {
        for(int i = 0 ; i < K; i++)
            cout << allEle[i] << "  ";
    }

	int swapVal = 0;

    BuildMinHeap(allEle, K);

    for(int i = K ; i < size; i++)
	{
		if(allEle[i] > allEle[0])
		{
			swapVal = allEle[i];
			allEle[i] = allEle[0];
			allEle[0] = swapVal;

			MinHeapify(allEle, 0, K-1);
		}
	}

	quickSort(allEle, 0, K-1);

	for(int i = K-1 ; i >= 0; i--)
		cout << allEle[i] << "  ";

}

void BuildMinHeap(int * m_array, const int heapSize)
{
	for(int rootIndex = heapSize/2 - 1 ; rootIndex  >= 0; rootIndex--)
	{
        MinHeapify(m_array, rootIndex, heapSize-1);
    }
}


void MinHeapify(int * m_array, int currentIndex, const int maxValidIndex)
{
    int swapVal = 0;

    int leftChildIndex = currentIndex * 2 + 1;
    int rightChildIndex = currentIndex * 2 + 2;
    
    int smallerIndex = currentIndex;

    if((leftChildIndex <= maxValidIndex) && (m_array[leftChildIndex] < m_array[smallerIndex]))
    {
        smallerIndex = leftChildIndex;
    }

    if((rightChildIndex <= maxValidIndex) && (m_array[rightChildIndex] < m_array[smallerIndex]))
    {
        smallerIndex = rightChildIndex;
    }

    if(smallerIndex != currentIndex)
    {
        swapVal = m_array[smallerIndex];
        m_array[smallerIndex] = m_array[currentIndex];
        m_array[currentIndex] = swapVal;

        MinHeapify(m_array , smallerIndex, maxValidIndex);
    }
}

